#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
private:
    void backtrack(vector<string>& result, string current, int left, int right, int n) {
        if ((left + right) == n * 2) { result.push_back(current); return; }
        if (left < n) { backtrack(result, current + "(", left + 1, right, n); }
        if (left < n) { backtrack(result, current + ")", left, right+1, n); }
    }
};